﻿using System;
using Xunit;
using Xunit.Abstractions;

namespace _001.日刷
{
    public class _1646_获取生成数组中的最大值
    {
        /// <summary>
        /// https://leetcode.cn/problems/get-maximum-in-generated-array/
        /// </summary>
        public class Solution
        {
            /// <summary>
            /// 2021-8-23 
            /// 执行用时：36 ms, 在所有 C# 提交中击败了80.95%的用户
            /// 内存消耗：14.7 MB, 在所有 C# 提交中击败了90.48%的用户
            /// </summary>
            /// <param name="n"></param>
            /// <returns></returns>
            public int GetMaximumGenerated(int n)
            {
                int max = 1;
                if (n <= 1) return n;
                int[] nums = new int[n + 1];
                nums[0] = 0;
                nums[1] = 1;

                for (var i = 1; 2 * i < n + 1 && 2 * i + 1 < n + 1; i += 1)
                {
                    if (2 * i < n + 1)
                    {
                        nums[2 * i] = nums[i];
                        max = Math.Max(max, nums[2 * i]);
                    }

                    if (2 * i + 1 < n + 1)
                    {
                        nums[2 * i + 1] = nums[i] + nums[i + 1];
                        max = Math.Max(max, nums[2 * i + 1]);
                    }
                }
                return max;

            }
        }


        ITestOutputHelper output;
        public _1646_获取生成数组中的最大值(ITestOutputHelper output)
        {
            this.output = output;
        }

        [Fact]
        public void Test1()
        {
            Solution S = new Solution();

            output.WriteLine("" + S.GetMaximumGenerated(7));
            output.WriteLine("" + S.GetMaximumGenerated(2));
            output.WriteLine("" + S.GetMaximumGenerated(3));
        }
    }
}
